package com.LeeCode;

public class Code279 {
    public static void main(String[] args) {
        int res = new Code279().numSquares1(13);
        System.out.println(res);
    }

    public int numSquares(int n) {
        int[] aux = new int[n]; // 动态规划数组

        for (int i = 1; i <= n; i++) {
            if (check(i)) { // 如果是完全平方数
                aux[i - 1] = 1;
            } else {
                int tmp = Integer.MAX_VALUE;
                for (int j = 1; j < Math.sqrt(i); j++) { // 遍历不小于i的所有完全平方数
                    tmp = Math.min(tmp, aux[i - j * j - 1] + 1);
                }
                aux[i - 1] = tmp;
            }
        }

        return aux[n - 1];
    }

    public boolean check(int num) {
        int sqrt = (int) Math.sqrt(num);
        return sqrt * sqrt == num;
    }

    public int numSquares1(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
}
